class _Node:
    """ List's item node """
    
    def __init__(self, pre_node=None, next_node=None, data=None):
        self.pre_node = pre_node
        self.next_node = next_node
        self.data = data

        
class list:
    """ Undirectional List implementation  """
    
    def __init__(self):
        self._first_node = _Node()
        self.size = 0

    def insert(self, index, obj):
        last_node = self._first_node
        current_node = self._first_node.next_node
        
        while current_node is not None:
            if index == 0:
                last_node.next_node = _Node(next_node=current_node, data=obj)
                break
            index = index - 1
            last_node = current_node
            current_node = current_node.next_node
        else:
            last_node.next_node = _Node(data=obj)

        self.size += 1

    def get(self, index):
        if index < 0:
            raise IndexError()
        
        current_node = self._first_node.next_node
        while current_node is not None:
            if index == 0:
                return current_node.data
            index = index - 1
            current_node = current_node.next_node
            
        else:
            raise IndexError()

        
    def remove(self, index):
        if index < 0:
            raise IndexError()

        last_node = self._first_node
        current_node = self._first_node.next_node
        while current_node is not None:
            if index == 0:
                last_node.next_node = current_node.next_node
                self.size -= 1
                return
            index -= 1
            last_node = current_node
            current_node = current_node.next_node
        else:
            raise IndexError()

    def __length__(self):
        return self.size
                

class DirectionalList:
    """ directional linked list impletamention  """

    def __init__(self):
        self._first_node = _Node()
        self._last_node = _Node(pre_node=self._first_node)
        self._first_node.next_node = self._last_node
        self.size = 0

    def insert(self, index, obj):
        if index < 0:
            raise IndexError()
        last_node = self._first_node
        current_node = self._first_node.next_node
        while current_node is not None and current_node is not self._last_node:
            if index == 0:
                last_node.next_node = _Node(pre_node=last_node, data=obj, next_node=current_node)
                current_node.pre_node = last_node.next_node
                break
            else:
                index -= 1
                last_node = current_node
                current_node = current_node.next_node
        else:
            last_node.next_node = _Node(pre_node=last_node, data=obj, next_node=self._last_node)
            self._last_node.pre_node = last_node.next_node

        self.size += 1        

    def rinsert(self, rindex, obj):
        if rindex < 0:
            raise IndexError()
        last_node = self._last_node
        current_node = self._last_node.pre_node
        while current_node is not None and current_node is not self._first_node:
            if rindex == 0:
                last_node.pre_node = _Node(pre_node= current_node, data=obj, next_node=last_node)
                current_node.next_node = last_node.pre_node
                break
            else:
                last_node = current_node.pre_node
                current_node = current_node.pre_node
                rindex -= 1
        else:
            last_node.pre_node = _Node(pre_node=self._first_node, data=obj, next_node=last_node)
            self._first_node.next_node = last_node.pre_node

        self.size += 1
            
    def get(self, index):
        if index < 0:
            raise IndexError()
        current_node = self._first_node.next_node
        while current_node is not None and current_node is not self._last_node:
            if index == 0:
                return current_node.data
            index -= 1
            current_node = current_node.next_node
        else:
            raise IndexError()

    def rget(self, rindex):
        if rindex < 0:
            raise IndexError()
        current_node = self._last_node.pre_node
        while current_node is not None and current_node is not self._first_node:
            if rindex == 0:
                return current_node.data
            rindex -= 1
            current_node = current_node.pre_node
        else:
            raise IndexError()
            
    def remove(self, index):
        if index < 0:
            raise IndexError()
        
        last_node = self._first_node
        current_node = self._first_node.next_node
        while current_node is not None and current_node is not self._last_node:
            if index == 0:
                next_node = current_node.next_node
                last_node.next_node = next_node
                next_node.pre_node = last_node
                self.size -= 1
                return current_node.data
            index -= 1
            last_node = current_node
            current_node = current_node.next_node
        else:
            raise IndexError()

    def rremove(self, rindex):
        if rindex < 0:
            raise IndexError()
        last_node = self._last_node
        current_node = self._last_node.pre_node
        while current_node is not None and current_node is not self._first_node:
            if rindex == 0:
                pre_node = current_node.pre_node
                pre_node.next_node = last_node
                last_node.pre_node = pre_node
                self.size -= 1
                return current_node.data
            rindex -= 1
            last_node = current_node
            current_node = current_node.pre_node
        else:
            raise IndexError()
